/*
 * bst/tree.hh - Simple binary search tree implementation.
 * Copyright (C) 2008  Mikhail Vorozhtsov
 * See the LICENSE section of the README file for details.
 */

/* $Id$ */

#ifndef HEADER_LIBBST_MJ_TREE_HH
#define HEADER_LIBBST_MJ_TREE_HH

#include HEADER (LIBBST_PREFIX,base.hh)

START_NAMESPACE (LIBBST_NS)

template <typename NODE, typename TREE, typename GLUE>
struct fwd_tree_t : public base_tree_t<NODE, TREE, GLUE>
{
public:
  template <typename STACK>
  bool
  insert (typename NODE::container_t *x, STACK &stack UNUSED)
  {
    NODE *parent, *prev_or_next;
    bool left_p;

    if (full_lookup (x, parent, left_p, prev_or_next))
      return false;

    NODE *n = (NODE *) NODE::from_container (x);
    before_insert (n, parent, left_p);
    n->insert (this, parent, left_p, prev_or_next);
    return true;
  }

  template <typename KEY, typename CMP, typename STACK>
  typename NODE::container_t *
  remove_key (const KEY &key, STACK &stack UNUSED)
  {
    NODE *parent, *prev_or_next;
    bool left_p;
    typename NODE::container_t *x
      = this->template full_lookup_key<KEY, CMP>
                         (key, parent, left_p, prev_or_next);

    if (!x)
      return NULL;

    NODE *n = (NODE *) NODE::from_container (x);
    NODE *left = (NODE *) n->get_left ();
    NODE *right = (NODE *) n->get_right ();

    if (left)
      {
        NODE *pred_parent = n;
        NODE *pred = left->get_max (pred_parent);
        NODE *succ = NULL;
        n->replace_with_pred (this, parent, left_p, pred, pred_parent, succ);
        after_remove (n, parent, pred, right != NULL, succ);
      }
    else if (right)
      {
        NODE *succ_parent = n;
        NODE *succ = right->get_min (succ_parent);
        n->replace_with_succ (this, parent, left_p, succ, succ_parent,
                              prev_or_next);
        after_remove (n, parent, NULL, true, succ);
      }
    else
      {
        n->remove (this, parent, left_p, prev_or_next);
        after_remove (n, parent, NULL, false, NULL);
      }

    return x;
  }
};

template <typename NODE, typename TREE = basic_tree_t, typename GLUE = glue_t>
class tree_t
  : public wrap_tree_t<ord_lookup_tree_t<fwd_tree_t<NODE, TREE, GLUE> > >
{
};

END_NAMESPACE

#endif /* HEADER_LIBBST_MJ_TREE_HH */

